package com.mlh.linkedlist;

/**
 * @author 缪林辉
 * @date 2024/8/21 11:36
 * @DESCRIPTION
 */
//给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
// k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
// 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
public class K个一组翻转链表 {
    public ListNode method1(ListNode head, int k) {
        //这边的思想是把要反转的k个节点截取出来，记录他的pre next节点 方便接回去
        //newHead是将要返回答案的新头的前一个节点
        ListNode pre=new ListNode(0);
        pre.next=head;
        ListNode tail,next,newHead=pre;
        while(true){
            tail=pre;
            for (int i = 0; i < k; i++) {
                tail=tail.next;
                if(tail==null){
                    return newHead.next;
                }
            }
            next=tail.next;
            //对tail next pre都赋值完成后，开始翻转
            ListNode[] reverse = reverse(pre.next, tail);
            pre.next=reverse[0];//接上反转后的新头
            reverse[1].next=next;//反转后的新尾接上
            pre=reverse[1];//重新设置pre
        }
    }
    public ListNode[]reverse(ListNode head,ListNode tail){
        ListNode newHead=tail,newTail=head,pre=null,next;
        while (pre!=tail){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return new ListNode[]{newHead,newTail};
    }

    public ListNode practice(ListNode head, int k) {
        ListNode headSentry=new ListNode(),tailSentry=new ListNode();
        headSentry.next=head;
        tailSentry.next=head;
        ListNode newHead=headSentry;
        while(true){
            for (int i = 0; i < k; i++) {
                tailSentry=tailSentry.next;
                if(tailSentry==null){
                    return newHead.next;
                }
            }
            ListNode temp=tailSentry.next;
            ListNode[] reverse = reverse(headSentry.next, tailSentry);
            headSentry.next=reverse[0];
            tailSentry=reverse[1];
            tailSentry.next=temp;
            headSentry=tailSentry;//把头换过来
        }
    }
}
